#pragma once



enum Colour
{
	RED,
	BLACK
};


template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	T _data;
	Colour _col;

	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
	{}
};
//迭代器
template<class T,class Ref,class Ptr>
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __RBTreeIterator<T, Ref, Ptr> Self;

	Node* _node;

	__RBTreeIterator(Node* node)
		:_node(node)
	{}
		
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	bool operator==(const Self& s)const
	{
		return _node == s._node;
	}
	bool operator!=(const Self& s)const
	{
		return _node != s._node;
	}
	//前置++	中序：左 根 右
	Self& operator++()
	{
		//如果存在右子树,下一个一定是右子树的最左结点，（因为进入下一颗右子树，中序第一个遍历的一定是左）
		if (_node->_right)
		{
			Node* left = _node->_right;
			while (left->_left)
			{
				left = left->_left;
			}
			_node = left;
		}
		else
		{
			//不存在右子树，那就找祖先里面孩子不是祖先右子树的那个祖先（孩子是祖先的左刚遍历完左，下一个就是根即祖先）
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && parent->_right == cur)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	//前置--
	Self& operator--()
	{
		//如果有左子树（意味当前为根，当前子树的开头，上一轮是左子树的遍历，最后一个位置是左子树的末尾），那么上一个位置一定是左子树的最右结点位置（上一棵子树的末尾）
		if (_node->_left)
		{
			//找上一颗最右结点
			Node* right = _node->_left;
			while (right->_right)
			{
				right = right->_right;
			}
			_node = right;
		}
		//没有左子树,找祖先里面孩子不是祖先左子树的那个祖先(找上一轮的根）
		else
		{
			Node* parent = _node->_parent;
			Node* cur = _node;

			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

};


template<class K, class T,class KeyOfT>
struct RBTree
{
	typedef RBTreeNode<T> Node;
	typedef __RBTreeIterator<T, T&, T*> iterator;
public:

	iterator begin()
	{
		//第一个结点位置是begin，即最左结点
		Node* left = _root;
		while (left && left->_left)
		{
			left = left->_left;
		}
		return iterator(left);
	}
	iterator end()
	{
		//最后一个结点的下一个位置是end，即最右结点的下一个为空,源码中是哨兵位
		return nullptr;
	}

	pair<iterator,bool> Insert(const T& data)
	{
		KeyOfT kot;
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root),true);
		}

		//记录parent，判断插入的结点是在parent的左子树还是右子树
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			//T有可能是set中的key，也可能是map中的pair<key,value>，如果是map中的，无法取第一个元素比较，所以要仿函数
			if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//相等则说明红黑树中已有，不需要再插入
				return make_pair(iterator(cur),false);
			}
		}
		//此时找到插入位置cur
		cur = new Node(data);
		Node* newnode = cur;
		cur->_col = RED;	//默认插入红色
		//判断cur在左子树还是右子树
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		//需要调整的条件：如果是parent存在(防止是根结点，产生野指针问题）且为红（不能有连续2个红，所以要调整）,满足两个条件可以继续向上调整（说明之前是一颗子树）
		while (parent && parent->_col == RED)
		{
			//记录下grandfather
			Node* grandfather = parent->_parent;
			assert(grandfather);
			assert(grandfather->_col == BLACK);//断言检查，grandfather规定为黑，如果不是则本身就不是红黑树了
			//处理情况，关键看叔叔uncle
			//三种情况默认：cur、p为红，g为黑！！！！
			//在左子树情况
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//情况一：uncle存在且为红，变色+向上继续调整
				if (uncle && uncle->_col == RED)
				{
					//p、u变黑，g变红
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					//更新，继续向上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				//uncle不存在+存在且为黑((p是g的左&&cur是p的左 )||(p是g的右&&cur是p的右))单旋+变色
				else
				{
					//情况二：右单旋+变色
					//		g					g
					//	 p     u			  p
					// c					c	
					if (cur == parent->_left)
					{
						//右单旋
						RotateR(grandfather);
						//变色
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					//情况三：左右双旋+变色
					//		g						g
					//	 p     u				p
					//		c						c
					else
					{
						RotateL(parent);
						//		g
						//	  c   u
						//  p
						RotateR(grandfather);
						//		c
						//	  p   g
						//          u
						cur->_col = BLACK;
						grandfather->_col = RED;

					}
					break;//一次调整就可以直接退出	
				}
			}
			//grandfather->_right==parent，总体相反情况，parent在grandfather的右
			else
			{
				Node* uncle = grandfather->_left;
				//情况一
				if (uncle && uncle->_col == RED)
				{
					//p、u变黑，g变红
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					//更新，继续向上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				//情况二+情况三
				else
				{
					//情况二：左单旋+变色
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						//变色
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					//情况三：右左双旋+变色
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}

		//（保留疑问）parent向上调整到刚好是根，无法进入循环调整，直接给_root变黑
		_root->_col = BLACK;
		return make_pair(iterator(newnode),true);
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	bool IsBalance()
	{
		if (_root == nullptr)
		{
			return true;
		}
		if (_root->_col == RED)
		{
			cout << "根节点不是黑色" << endl;
			return false;
		}
		//设置基准值
		int benchmark = 0;
		//前序遍历检查判断
		return PrevCheck(_root, 0, benchmark);
	}
private:
	bool PrevCheck(Node* root, int blackNum, int& benchmark)
	{
		if (root == nullptr)
		{
			//到达根结点，获取基准值
			if (benchmark == 0)
			{
				benchmark = blackNum;
				return true;
			}
			if (blackNum != benchmark)
			{
				cout << "某条路径黑色结点数目不够" << endl;
				return false;
			}
			else
			{
				return true;
			}
		}
		if (root->_col == BLACK)
		{
			++blackNum;
		}
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "存在连续的红色节点" << endl;
			return false;
		}

		return PrevCheck(root->_left, blackNum, benchmark)
			&& PrevCheck(root->_right, blackNum, benchmark);
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}
	//左旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		//旋转过去的parent要连接subRL
		parent->_right = subRL;
		if (subRL)
		{
			//如果subRL不是空结点，则要连接parent
			subRL->_parent = parent;
		}

		//记录旋转前parent的parent，判断该子树是上层的左子树还是右子树
		Node* ppNode = parent->_parent;

		//subR旋转上去
		subR->_left = parent;
		parent->_parent = subR;

		//如果不是子树，是根
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;//直接给空
		}
		//是子树，判断是左子树还是右子树
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
	}
	//右旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		//旋转过去的parent要连接subLR
		parent->_left = subLR;
		if (subLR)
		{
			//如果subLR不是空结点，则要连接parent
			subLR->_parent = parent;
		}

		//记录旋转前parent的parent，判断该子树是上层的左子树还是右子树
		Node* ppNode = parent->_parent;

		//subL旋转上去
		subL->_right = parent;
		parent->_parent = subL;

		//如果不是子树，是根
		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;//直接给空
		}
		//是子树，判断是左子树还是右子树
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
	}

private:
	Node* _root = nullptr;
};


//void TestRBTree1()
//{
//	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 0,5,30,25,20,4,13,30,28,27 };  // 测试双旋平衡因子调节
//	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//	RBTree<int, int> t1;
//	for (auto e : a)
//	{
//		t1.Insert(make_pair(e, e));
//	}
//
//	t1.InOrder();
//	cout << "IsBalance:" << t1.IsBalance() << endl;
//}
//
//void TestRBTree2()
//{
//	size_t N = 1000;
//	srand(time(0));
//	RBTree<int, int> t1;
//	for (size_t i = 0; i < N; ++i)
//	{
//		int x = rand();
//		cout << "Insert:" << x << ":" << i << endl;
//		t1.Insert(make_pair(x, i));
//	}
//	cout << "IsBalance:" << t1.IsBalance() << endl;
//}
